package LeetCode.month01.day24;

import java.util.Arrays;

public class No2787 {
    public static void main(String[] args) {
        System.out.println(numberOfWays(4,1));
    }
    public static int numberOfWays(int n, int x) {
        int[] dp = new int[n+1];
        dp[0]=1;
        for (int i = 1; i <=n; i++) {
            int val = (int)Math.pow(i,x);
            if(val>n)break;
            for (int j =n;j>=val;j--){
                dp[j]=(dp[j]+dp[j-val])%(int)(1e9+7);
            }
        }
        return dp[n];
    }
}
